//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //记忆化搜索
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        int n = triangle[0].size();
        vector<vector<int>> memo(m,vector<int>(n, INT_MAX));
        return dfs(triangle, 0, 0, memo);

    }
    int dfs(vector<vector<int>> &triangle, int i, int j, vector<vector<int>> & memo){
        if(i==triangle.size()){
            return 0;
        }

        if (memo[i][j]!=INT_MAX)return memo[i][j];

        int left = dfs(triangle, i+1, j,memo);
        int right = dfs(triangle, i+1, j+1, memo);
        memo[i][j] = min(left,right) + triangle[i][j];
        return memo[i][j];
    }

    int minimumTotal1(vector<vector<int>>& triangle) {
        int n = triangle.size();
        // dp[i][j] 表示从点 [i, j] 到底边的最小路径和。
        vector<vector<int>> dp(n, vector<int>(n));

        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangle[n - 1][i];
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }

    int minimumTotal2(vector<vector<int>>& triangle) {
        int n = triangle.size();
        // dp[i][j] 表示从点 [i, j] 到底边的最小路径和。
        vector<int> dp(n);

        for (int i = 0; i < n; i++) {
            dp[i] = triangle[n - 1][i];
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};